#include <iostream>

using namespace std;
// 69. x的平方根
// 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
// 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

// 二分搜索法
class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x;
        while (l < r) { // 这个条件很特殊
            long long mid = l + ((long long )r - l + 1) / 2;
            if(mid * mid <= (long long )x)
                l = mid;
            else
                r = mid - 1;
        }
        return l;
    }
};
int main() {
    cout << Solution().mySqrt(4) << endl;
    cout << Solution().mySqrt(8) << endl;
    return 0;
}
